剑指Offer题解 - Day58

剑指 Offer 20. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

1. 若干空格
2. 一个 小数 或者 整数
3. （可选）一个 'e' 或 'E' ，后面跟着一个 整数
4. 若干空格

小数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 下述格式之一：
   1. 至少一位数字，后面跟着一个点 '.'
   2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
   3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 至少一位数字

部分数值列举如下：

1. ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：

1. ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

示例 1：

输入：s = "e"
输出：false

示例 2：

输入：s = "."
输出：false

示例 3：

输入：s = "    .1  "
输出：true

提示：

• 1 <= s.length <= 20
• s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。

思路：

首先考虑使用正则匹配进行题解。

合法的字符包括：空格 「 」、数字「 0-9 」 、正负号 「 +、− 」 、小数点 「 . 」 、幂符号 「 e、E」

正则

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
    if (typeof s !== 'string') {
        return false;
    }
    return /^ *[\+\-]?((\d+|\.\d+|\d+\.\d+)(\.?(e|E)[\+\-]?\d+)?|\d+\.((e|E)[\+\-]?\d+)?) *$/.test(s)
};

正则可以通过提交，但是正则很容易产生性能问题，所以正则不是最优解。

状态机

本机可以使用 有限状态自动机 解决。题解参考自这里 (opens new window)。

按照字符串从左到右的顺序，定义以下 9 种状态。

0. 开始的空格

1. 幂符号前的正负号

2. 小数点前的数字

3. 小数点、小数点后的数字

4. 当小数点前为空格时，小数点、小数点后的数字

5. 幂符号

6. 幂符号后的正负号

7. 幂符号后的数字

8. 结尾的空格

其中，合法的结束状态有 2, 3, 7, 8 。

首先，需要设置状态转移表。按照上面分析的5种合法字符，分别使用以下缩写来表示：

• ' ' → 空格 「 」
• 'd' → 数字「 0-9 」
• 's' → 正负号 「 +、− 」
• '.' → 小数点 「 . 」
• 'e' → 幂符号 「 e、E」

设 states[i] ，其中 i 为所处状态， states[i] 使用哈希表存储可转移至的状态。键值对 (key, value) 含义：输入字符 key ，则从状态 i 转移至状态 value 。

初始化的状态值记为0。然后进行状态转移循环。

记录字符类型 t ： 分为四种情况。

1. 当 c 为正负号时，执行 t = 's' ;
2. 当 c 为数字时，执行 t = 'd' ;
3. 当 c 为 e 或 E 时，执行 t = 'e' ;
4. 当 c 为 . 或 空格 时，执行 t = c （即用字符本身表示字符类型）;
5. 否则，执行 t = '?' ，代表为不属于判断范围的非法字符，后续直接返回 false 。

终止条件： 若字符类型 t 不在哈希表 states[p] 中，说明无法转移至下一状态，因此直接返回 falsefalse 。 状态转移： 状态 p 转移至 states[p][t] 。

循环结束后， 如果状态属于2，3，7，8，则意味着合法，返回true；否则返回false。

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
    const states = new Map([
        [0, new Map([
            [' ', 0],
            ['s', 1],
            ['d', 2],
            ['.', 4],
        ])],
        [1, new Map([
            ['d', 2],
            ['.', 4],
        ])],
        [2, new Map([
            ['d', 2],
            ['.', 3],
            ['e', 5],
            [' ', 8],
        ])],
        [3, new Map([
            ['d', 3],
            ['e', 5],
            [' ', 8],
        ])],
        [4, new Map([
            ['d', 3]
        ])],
        [5, new Map([
            ['s', 6],
            ['d', 7]
        ])],
        [6, new Map([
            ['d', 7]
        ])],
        [7, new Map([
            ['d', 7],
            [' ', 8],
        ])],
        [8, new Map([
            [' ', 8]
        ])]
    ])
    let p = 0;
    let t = null;
    for (const c of s) {
        if(c >= '0' && c <= '9') t = 'd';
        else if(c === '+' || c === '-') t = 's';
        else if(c === 'e' || c === 'E') t = 'e';
        else if(c === '.' || c === ' ') t = c;
        else t = '?';
        if (!states.get(p).has(t)) return false;
        p = states.get(p).get(t);
    }
    return p === 2 || p === 3 || p === 7 || p === 8;
};

• 时间复杂度 O(n)。
• 空间复杂度 O(1)。

分析：

有限状态机的难点在于状态转移表。我们通过Map 来存储，只要最终状态属于2、3、7、8，我们就认为是合法数值字符串。

总结

本题考查合法数值字符串的判断。最优解是使用有限状态机解决。但是状态转移不容易想到，难度系数中等。